Division algorithm

In mathematics, and more particularly in arithmetic, the usual process of division of integers producing a quotient and a remainder can be specified precisely by a theorem stating that these exist uniquely with given properties. An integer division algorithm is any effective method for producing such quotient and remainder. Using the decimal notation of integers (or any other positional notation), long division provides a fairly efficient division algorithm, and other algorithms exist as well. The integer division algorithm is an important ingredient for other algorithms, such as the Euclidean algorithm for finding the greatest common divisor of two integers.

The term "division algorithm" is also used in abstract algebra for any effective procedure in a Euclidean domain that makes explicit their defining property, by producing for a given dividend and nonzero divisor a quotient and a remainder such that the remainder is smaller than the divisor in the appropriate sense.

Contents 1 Statement of theorem 2 Examples 3 A Proof 3.1 Existence 3.2 Uniqueness 4 An alternative proof 4.1 An inductive proof for the case a ≥ 0 and b > 0 5 Effectiveness

Statement of theorem

Specifically, the division algorithm states that given two integers a and b, with b ≠ 0, there exist unique integers q and r such that a = bq + r and 0 ≤ r < |b|, where |b| denotes the absolute value of b.

The integer

• q is called the quotient
• r is called the remainder
• b is called the divisor
• a is called the dividend

Examples

• If a = 7 and b = 3, then q = 2 and r = 1, since 7 = 2 × 3 + 1.
• If a = 7 and b = − 3, then q = − 2 and r = 1, since 7 = − 2 × (− 3) + 1.
• If a = − 7 and b = 3, then q = − 3 and r = 2, since − 7 = − 3 × 3 + 2.
• If a = − 7 and b = − 3, then q = 3 and r = 2, since − 7 = 3 × (− 3) + 2.

A Proof

The proof consists of two parts — first, the proof of the existence of q and r, and second, the proof of the uniqueness of q and r.

Existence

Consider the set

We claim that S contains at least one nonnegative integer. There are two cases to consider.

• If a is nonnegative, then choose n = 0.
• If a is negative, then choose n = ab.

In both cases, a - nb is nonnegative, and thus S always contains at least one nonnegative integer. This means we can apply the well-ordering principle, and deduce that S contains a least nonnegative integer r. By definition, r = a - nb for some n. Let q be this n. Then, by rearranging the equation, a = qb + r.

It only remains to show that 0 ≤ r < |b|. The first inequality holds because of the choice of r as a nonnegative integer. To show the last (strict) inequality, suppose that r ≥ |b|. Since b ≠ 0, r > 0, and again b > 0 or b < 0.

• If b > 0, then r ≥ b implies a-qb ≥ b. This implies that a-qb-b ≥0, further implying that a-(q+1)b ≥ 0. Therefore, a-(q+1)b is in S and, since a-(q+1)b=r-b with b>0 we know a-(q+1)b<r, contradicting the assumption that r was the least nonnegative element of S.

• If b < 0, then r ≥ -b implies that a-qb ≥ -b. This implies that a-qb+b ≥0, further implying that a-(q-1)b ≥ 0. Therefore, a-(q-1)b is in S and, since a-(q-1)b=r+b with b<0 we know a-(q-1)b<r, contradicting the assumption that r was the least nonnegative element of S.

In either case, we have shown that r > 0 was not really the least nonnegative integer in S, after all. This is a contradiction, and so we must have r < |b|. This completes the proof of the existence of q and r.

Uniqueness

Suppose there exists q, q' , r, r' with 0 ≤ r, r' < |b| such that a = bq + r and a = bq' + r' . Without loss of generality we may assume that q ≤ q' .

Subtracting the two equations yields: b(q' - q) = (r - r' ).

If b > 0 then r' ≤ r and r < b ≤ b + r' , and so (r - r' ) < b. Similarly, if b < 0 then r ≤ r' and r' < -b ≤ -b + r, and so -(r - r' ) < -b. Combining these yields |r - r' | < |b|.

The original equation implies that |b| divides |r - r' |; therefore either |b| ≤ |r - r' | or |r - r' | = 0. Because we just established that |r - r' | < |b|, by trichotomy we may conclude that the first possibility cannot hold. Thus, r = r' .

Substituting this into the original two equations quickly yields bq = bq' and, since we assumed b is not 0, it must be the case that q = q' proving uniqueness.

An alternative proof

First note that for any integers a, b, q, r, the relation a = bq + r is equivalent both to a = −b×−q + r and to −1 − a = b(−1 − q) + b − 1 − r, so that the pair (q,r) is a solution for the division of a by b if and only if (−q,r) is a solution for the division of a by −b, and also if and only if (−1 − q,b − 1 − r) is a solution for the division of −1 − a by b. It will therefore suffice to prove existence and uniqueness of these solutions assuming b > 0 and a ≥ 0: existence and uniqueness in the other cases will follow from it by these equivalences. We assume these inequalities henceforth, and observe that they imply that q ≥ 0 for any possible solution (as q ≤ −1 together with the required r < b would imply bq + r < 0).

Informally, one finds r by repeatedly subtracting b from a until finding a value less than b, and shows that it is the unique possibility for the remainder (the uniqueness of the quotient then follows). Formally this part of the proof is by induction, and establishes existence and uniqueness at the same time.

An inductive proof for the case a ≥ 0 and b > 0

For fixed divisor b one proceeds by induction on the size of the dividend a. All cases with a < b are taken together as the starting case for the induction (they include at the very least the case a = 0). In this case the pair q = 0 and r = a proves the existence part. For the uniqueness part consider q first: one cannot have a = bq + r with q > 0 and r ≥ 0 since a < b, so q = 0 is the only possible value, but then necessarily r = a − bq = a, so r is unique as well.

For the inductive step, suppose a ≥ b, and suppose the statement holds for all dividends less than a. In particular it holds for a − b, so there exist unique values q′ and r′ such that a − b = q′b + r′ and r′ < b. Now in order to have a = bq + r with r < b one cannot have q = 0, so necessarily q − 1 ≥ 0. The equation a = bq + r then is equivalent to

and by the statement for a − b this holds if and only if q − 1 = q′ and r = r′. So the pair given by q = q′ + 1 and r = r′ is the unique solution in this case, completing the proof.

Effectiveness

A proof of the theorem is not an algorithm to compute a quotient and a remainder. However, a recursive algorithm can be immediately obtained from the second proof. For the case of nonnegative dividend and divisor, it states that if a < b then q = 0 and r = a, and otherwise applies the algorithm recursively to a − b and b, and adds one to the quotient found for that case, keeping the same remainder. The results for one or more negative arguments are deduced from those for positive arguments as indicated in the proof. This is not a very efficient method, as it requires as many steps as the size of the quotient. This is related to the fact that it only uses the basic arithmetic operations and comparisons of the integers, as opposed to any particular representation of them such as decimal notation; this gives no access even to coarse estimates of the size of the operands, such as their number of digits, although such information will usually be available when concretely giving a and b. In terms of decimal notation, long division provides a much more efficient division algorithm.

By contrast, alternative algorithms that could be formulated in terms of operations on rational numbers or even on real numbers do not constitute useful division algorithms, since realizing such operations effectively requires being able to perform operations of integer arithmetic, and notably the integer division algorithm (to find the integral part of a rational number for instance).